﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodeTop.复习八月份
{
    public class Solution45
    {
        public int Jump2(int[] nums)//使用数组记录
        {
            int len = nums.Length;

            int[] times = new int[len];


            for (int i = 0; i < len; i++)
            {
                times[i]= len+1;
            }
          times[0] = 0;

                for (int i = 0; i < len; i++)
            {

                int curRange = nums[i];

                for (int j = 0; j <= curRange; j++)
                {

                    if(i+j < len)
                    {
                        times[i + j] = Math.Min(times[i + j], times[i] + 1);
                        Console.WriteLine(times[i + j]);
                       
                    }
                    
                }
            }

            return times[len - 1];

        }

        public int Jump3(int[] nums)//使用一个记录
        {
            int len = nums.Length;

            int stepCount = 0;
            int end = 1;
            int start = 0;
            int far = 0;
            while (end < len)
            {
            
                for (int i = start; i < end; i++) {


                    far = Math.Max(far, i + nums[i]);   
                
                
                }
                start = end ;
                end = far+1;
                stepCount++;


            }

            return stepCount;
          
           

        }

        public int Jump(int[] nums)//使用一个记录
        {
            int len = nums.Length;

            int stepCount = 0;
            int end = 0;           
            int far = 0;

                for (int i = 0; i < len-1; i++)
                {


                    far = Math.Max(far, i + nums[i]);

                if (i == end)//i==len-1,的时候已经到终点了，不需要再跳一次
                {
                    stepCount++;
                    end = far;
                }


                }
               
              


           

            return stepCount;



        }
       
    }

    class Program45
    {
        static void Main45(string[] args)
        {

            Solution45 s = new Solution45();
            int[] nums = [2, 3, 1, 1, 4];
         int res=   s.Jump(nums);
            Console.WriteLine(res);

        }
    }
}
